//队列的数组实现：头尾指针移动，重难点在于双指针
//如何布局双指针：
#include "Queue2.h"
#include <stdio.h>
#include <stdlib.h>

struct _queue {
    int head;
    int tail;
    ElementType* arr;
    int capacity;
    int size;
};

Queue* CreateQueue(int N) {
    Queue* q = (Queue*)malloc(sizeof(struct _queue));
    q->arr = (ElementType*)malloc(sizeof(ElementType) * N);
    q->head = 0;
    q->tail = 0;
    q->capacity = N;
    q->size = 0;
    return q;
}

void DisposeQueue(Queue* q) {
    if (q) {
        if (q->arr)
            free(q->arr);
        free(q);
    }
}

void EnQueue(Queue* q, ElementType ele) {
    if (q) {
        if (q->arr) {
            //非满入队
            if (!IsFull(q)) {
                if (IsEmpty(q)) {
                    q->arr[q->tail] = ele;
                    q->size++;
                } else {
                    if (q->tail == q->capacity - 1) {
                        q->tail = 0;
                        q->arr[q->tail] = ele;
                        q->size++;
                    } else {
                        q->arr[++(q->tail)] = ele;
                        q->size++;
                    }
                }
            }
        }
    }
}

ElementType DeQueue(Queue* q) {
    ElementType res = -1;
    if (q) {
        if (q->arr) {
            //非空出队
            if (!IsEmpty(q)) {
                if (q->head == q->tail) {
                    res = q->arr[q->head];
                    q->size--;
                } else {
                    if (q->head == q->capacity - 1) {
                        res = q->arr[q->head];
                        q->head = 0;
                        q->size--;
                    } else {
                        res = q->arr[q->head++];
                        q->size--;
                    }
                }
            }
        }
    }
    return res;
}

int IsEmpty(Queue* q) {
    if (q) {
        if (q->size > 0)
            return 0;
    }
    return 1;
}

int IsFull(Queue* q) {
    return q->size == q->capacity ? 1 : 0;
}

void EmptyQueue(Queue* q) {
    if (q) {
        if (q->arr) {
            q->head = 0;
            q->tail = 0;
            q->size = 0;
        }
    }
}

void TestQueue() {
    Queue* q = CreateQueue(7);
    for (int i = 0; i < 10; i++) {
        EnQueue(q, i);
    }
    while (!IsEmpty(q)) {
        printf("%d\n", DeQueue(q));
    }
    for (int i = 0; i < 10; i++) {
        EnQueue(q, i);
    }

    EmptyQueue(q);
    while (!IsEmpty(q)) {
        printf("%d\n", DeQueue(q));
    }
    DisposeQueue(q);
}
